require(GGally, quietly = TRUE)
require(reshape2, quietly = TRUE)
require(tidyverse, quietly = TRUE, warn.conflicts = FALSE)
package ‘tidyverse’ was built under R version 3.3.2package ‘tibble’ was built under R version 3.3.2package ‘tidyr’ was built under R version 3.3.2
library(ggfortify)
library(cluster)
library(ggdendro)
library(broom)
theme_set(theme_bw())
source("github-lib.R")
dw <- load_github_wide()
summary(dw)
repository_language ForkEvent IssuesEvent PushEvent
ActionScript: 1 Min. : 1.000 Min. : 1.000 Min. : 1.000
Ada : 1 1st Qu.: 1.509 1st Qu.: 3.437 1st Qu.: 7.052
Agda : 1 Median : 2.083 Median : 4.750 Median : 9.314
ANTLR : 1 Mean : 2.454 Mean : 7.311 Mean : 10.921
Apex : 1 3rd Qu.: 2.913 3rd Qu.: 7.269 3rd Qu.: 10.602
AppleScript : 1 Max. :18.000 Max. :63.000 Max. :154.250
(Other) :121
WatchEvent
Min. : 1.000
1st Qu.: 2.000
Median : 3.007
Mean : 3.725
3rd Qu.: 4.636
Max. :13.471
dw %>%
select(-repository_language) %>%
ggpairs()
plot: [1,1] [====---------------------------------------------------------] 6% est: 0s
plot: [1,2] [========-----------------------------------------------------] 12% est: 1s
plot: [1,3] [===========--------------------------------------------------] 19% est: 2s
plot: [1,4] [===============----------------------------------------------] 25% est: 1s
plot: [2,1] [===================------------------------------------------] 31% est: 1s
plot: [2,2] [=======================--------------------------------------] 38% est: 1s
plot: [2,3] [===========================----------------------------------] 44% est: 1s
plot: [2,4] [==============================-------------------------------] 50% est: 1s
plot: [3,1] [==================================---------------------------] 56% est: 1s
plot: [3,2] [======================================-----------------------] 62% est: 1s
plot: [3,3] [==========================================-------------------] 69% est: 1s
plot: [3,4] [==============================================---------------] 75% est: 0s
plot: [4,1] [==================================================-----------] 81% est: 0s
plot: [4,2] [=====================================================--------] 88% est: 0s
plot: [4,3] [=========================================================----] 94% est: 0s
plot: [4,4] [=============================================================]100% est: 0s

# XML e Bluespec têm mais de 50 pushes / repositório e
# outras linguagens têm também números estranhos. Filtraremos.
dw <- dw %>%
filter(PushEvent < 50, IssuesEvent < 50, ForkEvent < 18)
As variáveis são bastante assimétricas e concentradas em pequenos valores. Transformá-las para log ajuda na visualização.
summary(dw2.scaled)
repository_language ForkEvent IssuesEvent PushEvent
ActionScript: 1 Min. :-1.80630 Min. :-2.22415 Min. :-5.1947
Ada : 1 1st Qu.:-0.81777 1st Qu.:-0.46527 1st Qu.:-0.4681
Agda : 1 Median :-0.01687 Median :-0.02479 Median : 0.1830
ANTLR : 1 Mean : 0.00000 Mean : 0.00000 Mean : 0.0000
Apex : 1 3rd Qu.: 0.75644 3rd Qu.: 0.55363 3rd Qu.: 0.4992
AppleScript : 1 Max. : 2.56203 Max. : 2.76710 Max. : 2.7606
(Other) :115
WatchEvent cluster
Min. :-1.88615 Length:121
1st Qu.:-0.72590 Class :character
Median :-0.04339 Mode :character
Mean : 0.00000
3rd Qu.: 0.68503
Max. : 2.35217
dists = dw2.scaled %>%
column_to_rownames("repository_language") %>%
dist(method = "euclidean")
hc = hclust(dists, method = "ward.D")
plot(hc, cex = .6)

plot(hc, hang = -1)
n_clusters = 4
rect.hclust(hc, k=n_clusters)

dw2 <- dw2 %>%
mutate(cluster = hc %>%
cutree(k = n_clusters) %>%
as.character())
dw2.scaled <- dw2.scaled %>%
mutate(cluster = hc %>%
cutree(k = n_clusters) %>%
as.character())
dw2.long = melt(dw2.scaled, id.vars = c("repository_language", "cluster"))
hc %>%
cutree(k = n_clusters) %>%
silhouette(dists) %>%
plot(col = RColorBrewer::brewer.pal(n_clusters, "Set2"))

dw2.long %>%
ggplot(aes(x = variable, y = value, group = repository_language, colour = cluster)) +
geom_line(alpha = 0.4) +
facet_wrap(~ cluster)

library(plotly)
p <- dw2 %>%
plot_ly(type = 'parcoords',
line = list(color = ~cluster),
dimensions = list(
#list(range = c(1, 4), label = "cluster", values = ~cluster),
list(range = c(0, 4),
label = 'Sepal Width', values = ~ForkEvent),
list(range = c(0, 4),
constraintrange = c(5,6),
label = 'Sepal Length', values = ~IssuesEvent),
list(range = c(0, 4),
label = 'Petal Width', values = ~PushEvent),
list(range = c(0, 4),
label = 'Petal Length', values = ~WatchEvent)
)
)
p
k-means
table(km %>% pull(cluster))
Error in function_list[[k]](value) :
não foi possÃvel encontrar a função "pull"
Qual seria um bom valor de k? Uma medida comumente usada no kmeans é comparar a distância (quadrática) entre o centro dos clusters e o centro dos dados com a distância (quadrática) entre os pontos todos nos dados e o centro dos dados. Aqui o centro dos dados é um ponto imaginário na média de todas as variáveis. Calculamos a distância do centro de cada cluster para o centro dos dados e multiplicamos pelo número de pontos nesse cluster. Somando esse valor para todos os clusters, temos betweenss abaixo. Se esse valor for próximo do somatório total das distâncias dos pontos para o centro dos dados (totss), os pontos estão próximos do centro de seu cluster. Essa proporção pode ser usada para definir um bom valor de k. Quando ela para de crescer, para de valer à pena aumentar k.
set.seed(123)
explorando_k = tibble(k = 1:15) %>%
group_by(k) %>%
do(
kmeans(select(dw2.scaled, -repository_language),
centers = .$k,
nstart = 20) %>% glance()
)
explorando_k %>%
ggplot(aes(x = k, y = betweenss / totss)) +
geom_line() +
geom_point()

K-means
filmes = readr::read_csv("dados/filmes-scarlett-johanssson.csv")
Parsed with column specification:
cols(
RATING = col_double(),
TITLE = col_character(),
CREDIT = col_character(),
`BOX OFFICE` = col_double(),
YEAR = col_integer()
)

Mais um exemplo
O dataset ruspini é clássico para ilustrar agrupamento.

Hierárquico
dists = dist(rs, method = "euclidean")
hc = hclust(dists, method = "ward.D")
plot(hc, hang = -1, cex = 0.8)
rect.hclust(hc, k=4)
rs$cluster = factor(cutree(hc, k=4))
ggplot(rs, aes(x = x, y = y, colour = cluster)) +
geom_point(size = 3)
rs$cluster = factor(cutree(hc, k=8))
ggplot(rs, aes(x = x, y = y, colour = cluster, label = cluster)) +
geom_point(size = 2) +
geom_text(hjust = -.1, vjust = 1) +
xlim(0, 150)
plot(silhouette(cutree(hc, k = 4), dists))
plot(silhouette(cutree(hc, k = 6), dists))
#heatmap(as.matrix(dw2[,1:4]), Colv=F, scale='none')
#hc.data <- dendro_data(hc)
#ggdendrogram(hc.data, rotate = TRUE) +
#labs(title = "Agrupamento de Rustini")
km <- kmeans(rs, centers=4, nstart=10)
km
autoplot(km, data = rs)
autoplot(km, data = rs, frame = TRUE)
LS0tCnRpdGxlOiAiS21lYW5zIGUgbWFpcyBleGVtcGxvcyIKYXV0aG9yOiAiTmF6YXJlbm8gQW5kcmFkZSIKZGF0ZTogIjMwIGRlIG1hcsOnbyBkZSAyMDE2IgpvdXRwdXQ6IAogICAgaHRtbF9ub3RlYm9vawplZGl0b3Jfb3B0aW9uczogCiAgY2h1bmtfb3V0cHV0X3R5cGU6IGlubGluZQotLS0KCmBgYHtyLCBtZXNzYWdlPUZBTFNFfQpyZXF1aXJlKEdHYWxseSwgcXVpZXRseSA9IFRSVUUpCnJlcXVpcmUocmVzaGFwZTIsIHF1aWV0bHkgPSBUUlVFKQpyZXF1aXJlKHRpZHl2ZXJzZSwgcXVpZXRseSA9IFRSVUUsIHdhcm4uY29uZmxpY3RzID0gRkFMU0UpCmxpYnJhcnkoZ2dmb3J0aWZ5KQpsaWJyYXJ5KGNsdXN0ZXIpCmxpYnJhcnkoZ2dkZW5kcm8pCmxpYnJhcnkoYnJvb20pCgp0aGVtZV9zZXQodGhlbWVfYncoKSkKc291cmNlKCJnaXRodWItbGliLlIiKQpgYGAKCmBgYHtyfQpkdyA8LSBsb2FkX2dpdGh1Yl93aWRlKCkKc3VtbWFyeShkdykKCmR3ICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgojIFhNTCBlIEJsdWVzcGVjIHTDqm0gbWFpcyBkZSA1MCBwdXNoZXMgLyByZXBvc2l0w7NyaW8gZSAKIyBvdXRyYXMgbGluZ3VhZ2VucyB0w6ptIHRhbWLDqW0gbsO6bWVyb3MgZXN0cmFuaG9zLiBGaWx0cmFyZW1vcy4KZHcgPC0gZHcgJT4lIAogIGZpbHRlcihQdXNoRXZlbnQgPCA1MCwgSXNzdWVzRXZlbnQgPCA1MCwgRm9ya0V2ZW50IDwgMTgpCmBgYAoKQXMgdmFyacOhdmVpcyBzw6NvIGJhc3RhbnRlIGFzc2ltw6l0cmljYXMgZSBjb25jZW50cmFkYXMgZW0gcGVxdWVub3MgdmFsb3Jlcy4gVHJhbnNmb3Jtw6EtbGFzIHBhcmEgbG9nIGFqdWRhIG5hIHZpc3VhbGl6YcOnw6NvLgoKYGBge3J9CiMgRXNjYWxhIGRlIGxvZyAKZHcyIDwtIGR3ICU+JSAKICAgIG11dGF0ZV9lYWNoKGZ1bnMobG9nKSwgMjo1KQoKZHcyICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAgZ2dwYWlycygpCgpzdW1tYXJ5KHNlbGVjdChkdzIsIC1yZXBvc2l0b3J5X2xhbmd1YWdlKSkKCmR3Mi5zY2FsZWQgPSBkdzIgJT4lIAogIG11dGF0ZV9lYWNoKGZ1bnMoYXMudmVjdG9yKHNjYWxlKC4pKSksIDI6NSkKc3VtbWFyeShkdzIuc2NhbGVkKQpgYGAKCgpgYGB7cn0KZGlzdHMgPSBkdzIuc2NhbGVkICU+JSAKICAgIGNvbHVtbl90b19yb3duYW1lcygicmVwb3NpdG9yeV9sYW5ndWFnZSIpICU+JSAKICAgIGRpc3QobWV0aG9kID0gImV1Y2xpZGVhbiIpCmhjID0gaGNsdXN0KGRpc3RzLCBtZXRob2QgPSAid2FyZC5EIikKCnBsb3QoaGMsIGNleCA9IC42KQpwbG90KGhjLCBoYW5nID0gLTEpCgpuX2NsdXN0ZXJzID0gNApyZWN0LmhjbHVzdChoYywgaz1uX2NsdXN0ZXJzKQoKZHcyIDwtIGR3MiAlPiUgCiAgICBtdXRhdGUoY2x1c3RlciA9IGhjICU+JSAKICAgICAgICAgICAgICAgY3V0cmVlKGsgPSBuX2NsdXN0ZXJzKSAlPiUgCiAgICAgICAgICAgICAgIGFzLmNoYXJhY3RlcigpKQoKZHcyLnNjYWxlZCA8LSBkdzIuc2NhbGVkICU+JSAKICAgIG11dGF0ZShjbHVzdGVyID0gaGMgJT4lIAogICAgICAgICAgICAgICBjdXRyZWUoayA9IG5fY2x1c3RlcnMpICU+JSAKICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKCkpCgpkdzIubG9uZyA9IG1lbHQoZHcyLnNjYWxlZCwgaWQudmFycyA9IGMoInJlcG9zaXRvcnlfbGFuZ3VhZ2UiLCAiY2x1c3RlciIpKQoKaGMgJT4lIAogICAgY3V0cmVlKGsgPSBuX2NsdXN0ZXJzKSAlPiUgCiAgICBzaWxob3VldHRlKGRpc3RzKSAlPiUgCiAgICBwbG90KGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbChuX2NsdXN0ZXJzLCAiU2V0MiIpKQoKZHcyLmxvbmcgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gdmFyaWFibGUsIHkgPSB2YWx1ZSwgZ3JvdXAgPSByZXBvc2l0b3J5X2xhbmd1YWdlLCBjb2xvdXIgPSBjbHVzdGVyKSkgKyAKICAgIGdlb21fbGluZShhbHBoYSA9IDAuNCkgKyAKICAgIGZhY2V0X3dyYXAofiBjbHVzdGVyKSAKCmBgYAoKYGBge3J9CmxpYnJhcnkocGxvdGx5KQpwIDwtIGR3MiAlPiUKICAgIHBsb3RfbHkodHlwZSA9ICdwYXJjb29yZHMnLAogICAgICAgICAgICBsaW5lID0gbGlzdChjb2xvciA9IH5jbHVzdGVyKSwKICAgICAgICAgICAgZGltZW5zaW9ucyA9IGxpc3QoCiAgICAgICAgICAgICAgICAjbGlzdChyYW5nZSA9IGMoMSwgNCksIGxhYmVsID0gImNsdXN0ZXIiLCB2YWx1ZXMgPSB+Y2x1c3RlciksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygwLCA0KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnRm9ya3MvcmVwbycsIHZhbHVlcyA9IH5Gb3JrRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGNvbnN0cmFpbnRyYW5nZSA9IGMoNSw2KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnSXNzdWVzL3JlcG8nLCB2YWx1ZXMgPSB+SXNzdWVzRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoMCwgNCksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ1B1c2hlcy9yZXBvJywgdmFsdWVzID0gflB1c2hFdmVudCksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygwLCA0KSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnV2F0Y2hlcy9yZXBvJywgdmFsdWVzID0gfldhdGNoRXZlbnQpCiAgICAgICAgICAgICkKICAgICkKcApgYGAKCgojIyBrLW1lYW5zCgpgYGB7cn0KZHcyLnNjYWxlZCA9IGR3Mi5zY2FsZWQgJT4lIAogICAgc2VsZWN0KC1jbHVzdGVyKSAjIFJlbW92ZSBvIGNsdXN0ZXIgYWRpY2lvbmFkbyBhbnRlcyBsw6EgZW0gY2ltYSB2aWEgaGNsdXN0CgojIE8gYWdydXBhbWVudG8gZGUgZmF0bzoKa20gPSBkdzIuc2NhbGVkICU+JSAKICAgIHNlbGVjdCgtcmVwb3NpdG9yeV9sYW5ndWFnZSkgJT4lIAogICAga21lYW5zKGNlbnRlcnMgPSBuX2NsdXN0ZXJzLCBuc3RhcnQgPSAyMCkKCiMgTyBkZiBlbSBmb3JtYXRvIGxvbmdvLCBwYXJhIHZpc3VhbGl6YcOnw6NvIApkdzIuc2NhbGVkLmttLmxvbmcgPSBrbSAlPiUgCiAgICBhdWdtZW50KGR3Mi5zY2FsZWQpICU+JSAjIEFkaWNpb25hIG8gcmVzdWx0YWRvIGRlIGttIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBhb3MgZGFkb3Mgb3JpZ2luYWlzIGR3Mi5zY2FsZWQgZW0gCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHVtYSB2YXJpw6F2ZWwgY2hhbWFkYSAuY2x1c3RlcgogICAgZ2F0aGVyKGtleSA9ICJ2YXJpw6F2ZWwiLCAKICAgICAgICAgICB2YWx1ZSA9ICJ2YWxvciIsIAogICAgICAgICAgIC1yZXBvc2l0b3J5X2xhbmd1YWdlLCAtLmNsdXN0ZXIpICMgPSBtb3ZlIHBhcmEgbG9uZyB0b2RhcyBhcyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHZhcmnDoXZpZXMgbWVub3MgcmVwb3NpdG9yeV9sYW5ndWFnZSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIGUgLmNsdXN0ZXIKCmR3Mi5zY2FsZWQua20ubG9uZyAlPiUgCiAgICBnZ3Bsb3QoYWVzKHggPSBgdmFyacOhdmVsYCwgeSA9IHZhbG9yLCBncm91cCA9IHJlcG9zaXRvcnlfbGFuZ3VhZ2UsIGNvbG91ciA9IC5jbHVzdGVyKSkgKyAKICAgIGdlb21fcG9pbnQoYWxwaGEgPSAwLjIpICsgCiAgICBnZW9tX2xpbmUoYWxwaGEgPSAuNSkgKyAKICAgIGZhY2V0X3dyYXAofiAuY2x1c3RlcikgCgphdXRvcGxvdChrbSwgZGF0YSA9IGR3Mi5zY2FsZWQsIGxhYmVsID0gVFJVRSkKCmRpc3RzID0gZHcyLnNjYWxlZCAlPiUgCiAgICBzZWxlY3QoLXJlcG9zaXRvcnlfbGFuZ3VhZ2UpICU+JSAKICAgIGRpc3QoKSAjIHPDsyBwYXJhIHBsb3RhciBzaWxob3VldGFzIGRlcG9pcwpwbG90KHNpbGhvdWV0dGUoa20kY2x1c3RlciwgZGlzdHMpLCBjb2wgPSBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwobl9jbHVzdGVycywgIlNldDIiKSkKCnRhYmxlKGttICU+JSBwdWxsKGNsdXN0ZXIpKQpgYGAKCmBgYHtyfQojc3VtbWFyeShkdzIuc2NhbGVkKQpwIDwtIGttICU+JSAKICAgIGF1Z21lbnQoZHcyLnNjYWxlZCkgJT4lCiAgICBwbG90X2x5KHR5cGUgPSAncGFyY29vcmRzJywKICAgICAgICAgICAgbGluZSA9IGxpc3QoY29sb3IgPSB+LmNsdXN0ZXIsIAogICAgICAgICAgICAgICAgICAgICAgICBzaG93U2NhbGUgPSBUUlVFKSwKICAgICAgICAgICAgZGltZW5zaW9ucyA9IGxpc3QoCiAgICAgICAgICAgICAgICAjbGlzdChyYW5nZSA9IGMoMSwgNCksIGxhYmVsID0gImNsdXN0ZXIiLCB2YWx1ZXMgPSB+Y2x1c3RlciksCiAgICAgICAgICAgICAgICBsaXN0KHJhbmdlID0gYygtMywgMyksCiAgICAgICAgICAgICAgICAgICAgIGxhYmVsID0gJ0ZvcmtzL3JlcG8nLCB2YWx1ZXMgPSB+Rm9ya0V2ZW50KSwKICAgICAgICAgICAgICAgIGxpc3QocmFuZ2UgPSBjKC0zLCAzKSwKICAgICAgICAgICAgICAgICAgICAgbGFiZWwgPSAnSXNzdWVzL3JlcG8nLCB2YWx1ZXMgPSB+SXNzdWVzRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoLTYsIDMpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdQdXNoZXMvcmVwbycsIHZhbHVlcyA9IH5QdXNoRXZlbnQpLAogICAgICAgICAgICAgICAgbGlzdChyYW5nZSA9IGMoLTIsIDMpLAogICAgICAgICAgICAgICAgICAgICBsYWJlbCA9ICdXYXRjaGVzL3JlcG8nLCB2YWx1ZXMgPSB+V2F0Y2hFdmVudCkKICAgICAgICAgICAgKQogICAgKQpwCgpgYGAKClF1YWwgc2VyaWEgdW0gYm9tIHZhbG9yIGRlIGs/IFVtYSBtZWRpZGEgY29tdW1lbnRlIHVzYWRhIG5vIGttZWFucyDDqSBjb21wYXJhciBhIGRpc3TDom5jaWEgKHF1YWRyw6F0aWNhKSBlbnRyZSBvIGNlbnRybyBkb3MgY2x1c3RlcnMgZSBvIGNlbnRybyBkb3MgZGFkb3MgY29tIGEgZGlzdMOibmNpYSAocXVhZHLDoXRpY2EpIGVudHJlIG9zIHBvbnRvcyB0b2RvcyBub3MgZGFkb3MgZSBvIGNlbnRybyBkb3MgZGFkb3MuIEFxdWkgbyBjZW50cm8gZG9zIGRhZG9zIMOpIHVtIHBvbnRvIGltYWdpbsOhcmlvIG5hIG3DqWRpYSBkZSB0b2RhcyBhcyB2YXJpw6F2ZWlzLiBDYWxjdWxhbW9zIGEgZGlzdMOibmNpYSBkbyBjZW50cm8gZGUgY2FkYSBjbHVzdGVyIHBhcmEgbyBjZW50cm8gZG9zIGRhZG9zIGUgbXVsdGlwbGljYW1vcyBwZWxvIG7Dum1lcm8gZGUgcG9udG9zIG5lc3NlIGNsdXN0ZXIuIFNvbWFuZG8gZXNzZSB2YWxvciBwYXJhIHRvZG9zIG9zIGNsdXN0ZXJzLCB0ZW1vcyBgYmV0d2VlbnNzYCBhYmFpeG8uIFNlIGVzc2UgdmFsb3IgZm9yIHByw7N4aW1vIGRvIHNvbWF0w7NyaW8gdG90YWwgZGFzIGRpc3TDom5jaWFzIGRvcyBwb250b3MgcGFyYSBvIGNlbnRybyBkb3MgZGFkb3MgKGB0b3Rzc2ApLCBvcyBwb250b3MgZXN0w6NvIHByw7N4aW1vcyBkbyBjZW50cm8gZGUgc2V1IGNsdXN0ZXIuIApFc3NhIHByb3BvcsOnw6NvIHBvZGUgc2VyIHVzYWRhIHBhcmEgZGVmaW5pciB1bSBib20gdmFsb3IgZGUgYGtgLiBRdWFuZG8gZWxhIHBhcmEgZGUgY3Jlc2NlciwgcGFyYSBkZSB2YWxlciDDoCBwZW5hIGF1bWVudGFyIGBrYC4KCmBgYHtyfQpzZXQuc2VlZCgxMjMpCmV4cGxvcmFuZG9fayA9IHRpYmJsZShrID0gMToxNSkgJT4lIAogICAgZ3JvdXBfYnkoaykgJT4lIAogICAgZG8oCiAgICAgICAga21lYW5zKHNlbGVjdChkdzIuc2NhbGVkLCAtcmVwb3NpdG9yeV9sYW5ndWFnZSksIAogICAgICAgICAgICAgICBjZW50ZXJzID0gLiRrLCAKICAgICAgICAgICAgICAgbnN0YXJ0ID0gMjApICU+JSBnbGFuY2UoKQogICAgKQoKZXhwbG9yYW5kb19rICU+JSAKICAgIGdncGxvdChhZXMoeCA9IGssIHkgPSBiZXR3ZWVuc3MgLyB0b3RzcykpICsgCiAgICBnZW9tX2xpbmUoKSArIAogICAgZ2VvbV9wb2ludCgpCmBgYAoKCi0tLS0tLS0tLS0tLS0tLS0tLS0tCgoKIyMgSy1tZWFucwoKYGBge3J9CmZpbG1lcyA9IHJlYWRyOjpyZWFkX2NzdigiZGFkb3MvZmlsbWVzLXNjYXJsZXR0LWpvaGFuc3Nzb24uY3N2IikKCmZpbG1lc190ID0gZmlsbWVzICU+JSAKICAgIHNlbGVjdCgtQ1JFRElUKSAlPiUgCiAgICBtdXRhdGUoYEJPWCBPRkZJQ0VgID0gbG9nMTAoYEJPWCBPRkZJQ0VgKSkgJT4lIAogICAgbXV0YXRlX2VhY2goZnVucyhhcy52ZWN0b3Ioc2NhbGUoLikpKSwgYEJPWCBPRkZJQ0VgLCBSQVRJTkcpCgphdHJpYnVpY29lcyA9IHRpYmJsZShrID0gMTo2KSAlPiUgCiAgICBncm91cF9ieShrKSAlPiUgCiAgICBkbyhrbWVhbnMoc2VsZWN0KGZpbG1lc190LCBSQVRJTkcsIGBCT1ggT0ZGSUNFYCksIAogICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgIG5zdGFydCA9IDEwKSAlPiUgYXVnbWVudChmaWxtZXMpKSAjIGFsdGVybmUgZW50cmUgZmlsbWVzIGUgZmlsbWVzX3Qgbm8gYXVnbWVudCAgCgphdHJpYnVpY29lc19sb25nID0gYXRyaWJ1aWNvZXMgJT4lIAogICAgZ2F0aGVyKGtleSA9ICJ2YXJpYXZlbCIsIHZhbHVlID0gInZhbG9yIiwgLVRJVExFLCAtaywgLS5jbHVzdGVyLCAtQ1JFRElUKSAKCmF0cmlidWljb2VzICU+JQogICAgZ2dwbG90KGFlcyh4ID0gUkFUSU5HLCB5ID0gYEJPWC5PRkZJQ0VgLCBsYWJlbCA9IFRJVExFLCBjb2xvdXIgPSAuY2x1c3RlcikpICsgCiAgICBnZW9tX3BvaW50KCkgKyAKICAgICNnZW9tX3RleHQoKSArIAogICAgZmFjZXRfd3JhcCh+IGspCiAgICAjKyBzY2FsZV95X2xvZzEwKCkKCiMgQSBzaWxob3VldGEKZGlzdHMgPSBzZWxlY3QoZmlsbWVzX3QsIFJBVElORywgYEJPWCBPRkZJQ0VgKSAlPiUgZGlzdCgpCmttID0ga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgUkFUSU5HLCBgQk9YIE9GRklDRWApLCAKICAgICAgICAgICAgY2VudGVycyA9IDQsIAogICAgICAgICAgICBuc3RhcnQgPSAxMCkgCgpzaWxob3VldHRlKGttJGNsdXN0ZXIsIGRpc3RzKSAlPiUgCiAgICBwbG90KGNvbCA9IFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg0LCAiU2V0MiIpKQpgYGAKCmBgYHtyfQpzZXQuc2VlZCgxMjMpCmV4cGxvcmFuZG9fayA9IHRpYmJsZShrID0gMToxNSkgJT4lIAogICAgZ3JvdXBfYnkoaykgJT4lIAogICAgZG8oCiAgICAgICAga21lYW5zKHNlbGVjdChmaWxtZXNfdCwgLVRJVExFKSwgCiAgICAgICAgICAgICAgIGNlbnRlcnMgPSAuJGssIAogICAgICAgICAgICAgICBuc3RhcnQgPSAyMCkgJT4lIGdsYW5jZSgpCiAgICApCgpleHBsb3JhbmRvX2sgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IGJldHdlZW5zcyAvIHRvdHNzKSkgKyAKICAgIGdlb21fbGluZSgpICsgCiAgICBnZW9tX3BvaW50KCkKCmBgYAoKCiMgTWFpcyB1bSBleGVtcGxvCgpPIGRhdGFzZXQgcnVzcGluaSDDqSBjbMOhc3NpY28gcGFyYSBpbHVzdHJhciBhZ3J1cGFtZW50by4KCmBgYHtyfQpzdHIocnVzcGluaSkKCmdncGxvdChydXNwaW5pLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKc3VtbWFyeShydXNwaW5pKQoKcnMgPC0gZGF0YS5mcmFtZSgocnVzcGluaSkpCnJzIDwtIGRhdGEuZnJhbWUoc2NhbGUocnVzcGluaSkpCmNvbE1lYW5zKHJzKQoKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KHNpemUgPSAzKQoKYGBgCgojIyBIaWVyw6FycXVpY28KCmBgYHtyfQpkaXN0cyA9IGRpc3QocnMsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQpoYyA9IGhjbHVzdChkaXN0cywgbWV0aG9kID0gIndhcmQuRCIpCgpwbG90KGhjLCBoYW5nID0gLTEsIGNleCA9IDAuOCkKCnJlY3QuaGNsdXN0KGhjLCBrPTQpCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz00KSkKCmdncGxvdChycywgYWVzKHggPSB4LCB5ID0geSwgY29sb3VyID0gY2x1c3RlcikpICsgCiAgZ2VvbV9wb2ludChzaXplID0gMykgCgpycyRjbHVzdGVyID0gZmFjdG9yKGN1dHJlZShoYywgaz04KSkKZ2dwbG90KHJzLCBhZXMoeCA9IHgsIHkgPSB5LCBjb2xvdXIgPSBjbHVzdGVyLCBsYWJlbCA9IGNsdXN0ZXIpKSArIAogIGdlb21fcG9pbnQoc2l6ZSA9IDIpICsgCiAgZ2VvbV90ZXh0KGhqdXN0ID0gLS4xLCB2anVzdCA9IDEpICsgCiAgeGxpbSgwLCAxNTApCgpwbG90KHNpbGhvdWV0dGUoY3V0cmVlKGhjLCBrID0gNCksIGRpc3RzKSkKcGxvdChzaWxob3VldHRlKGN1dHJlZShoYywgayA9IDYpLCBkaXN0cykpCgojaGVhdG1hcChhcy5tYXRyaXgoZHcyWywxOjRdKSwgQ29sdj1GLCBzY2FsZT0nbm9uZScpCiNoYy5kYXRhIDwtIGRlbmRyb19kYXRhKGhjKQojZ2dkZW5kcm9ncmFtKGhjLmRhdGEsIHJvdGF0ZSA9IFRSVUUpICsgCiAgI2xhYnModGl0bGUgPSAiQWdydXBhbWVudG8gZGUgUnVzdGluaSIpCmBgYAoKYGBge3J9CmttIDwtIGttZWFucyhycywgY2VudGVycz00LCBuc3RhcnQ9MTApCmttCgphdXRvcGxvdChrbSwgZGF0YSA9IHJzKQoKYXV0b3Bsb3Qoa20sIGRhdGEgPSBycywgZnJhbWUgPSBUUlVFKQoKYGBgCgo=